package algo.A04_快速排序和归并排序;

import util.ArrayUtil;

/**
 * 在非负数组（乱序）中找到最小的可分配的id（从1开始编号），数据量1000000
 */
public class T05_最小可用ID_开辟额外空间 {
    public static void main(String[] args) {
        int max = 20;
        int[] arr = ArrayUtil.getRandomArrWithoutRepetition(max - 2,1,max);
        ArrayUtil.print(arr);
        int result = solution(arr,max);
        System.out.println("result = " + result);
    }

    //解题思路：数组哈希，将元素的值作为下标放在另一个数组中作为哈希表
    private static int solution(int[] arr,int max){
        boolean[] helper = new boolean[max + 1];
        for (int i : arr) {
            helper[i] = true;
        }
        for (int i = 1; i < helper.length; i++) {
            if (!helper[i]){
                return i;
            }
        }
        return arr.length + 1;
    }
}
